package util

type LRUCache struct {
	size       int
	cap        int
	cache      map[string]*DLinkedNode
	head, tail *DLinkedNode
}

type DLinkedNode struct {
	key       string
	val       interface{}
	pre, next *DLinkedNode
}

func InitDLinkedNode(key string, val interface{}) *DLinkedNode {
	return &DLinkedNode{key: key,
		val: val}
}

func Constructor(capacity int) LRUCache {
	l := LRUCache{
		cap:   capacity,
		cache: map[string]*DLinkedNode{},
		head:  InitDLinkedNode("", 0),
		tail:  InitDLinkedNode("", 0),
	}
	l.head.next = l.tail
	l.tail.pre = l.head
	return l
}

func (this *LRUCache) Get(key string) (interface{}, bool) {
	if node, ok := this.cache[key]; !ok {
		return nil, false
	} else {
		this.moveToHead(node)
		return node.val, true
	}
}

func (this *LRUCache) Put(key string, value interface{}) {
	if _, ok := this.cache[key]; !ok {
		node := InitDLinkedNode(key, value)
		this.addToHead(node)
		this.cache[key] = node
		this.size += 1
		if this.size > this.cap {
			node := this.removeTail()
			delete(this.cache, node.key)
			this.size -= 1
		}

	} else {
		node := this.cache[key]
		node.val = value
		this.moveToHead(node)
	}
}

func (this *LRUCache) addToHead(node *DLinkedNode) {
	node.next = this.head.next
	this.head.next.pre = node
	this.head.next = node
	node.pre = this.head
}

func (this *LRUCache) moveToHead(node *DLinkedNode) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache) removeNode(node *DLinkedNode) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

func (this *LRUCache) removeTail() *DLinkedNode {
	node := this.tail.pre
	this.removeNode(node)
	return node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
